package graph;

import union.UnionFind;

import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;

/**
 * @Author: LDeng
 * @Date: 2021-04-02 10:22
 */
public class ListGraph<V, E> extends Graph<V, E> {
    //存放图的所有的顶点
    private Map<V, Vertex<V, E>> vertices = new HashMap<>();
    //存放图的所有的边
    private Set<Edge<V, E>> edges = new HashSet<>();

    public ListGraph() {
        super();
    }

    public ListGraph(WeightManager<E> weightManager) {
        super(weightManager);
    }

    //边的比较器
    private Comparator<Edge<V, E>> edgeComparator = (Edge<V, E> e1, Edge<V, E> e2) -> {
        return weightManager.compare(e1.weight, e2.weight);
    };


    @Override
    public int edgesSize() {
        return edges.size();
    }

    @Override
    public int verticesSize() {
        return vertices.size();
    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {
        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            vertices.put(from, fromVertex);
        }
        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            vertices.put(to, toVertex);
        }
        //创建一条从fromVertex到toVertex的边，
        //判断判断原来从fromVertex中出去的边里面是否有相同的边
        //利用重写equals方法和重写hashCode方法去判断对象是否相同
        //因为hashSet判断标准就是equals()
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        edge.weight = weight;
        //更新权值操作：
        //这里不用判断contains，直接删除原先的边， 再创建新的边
        //删除之前fromVertex到toVertex的边 双边删
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            //删除存放所有边的edges成员变量中的edge
            edges.remove(edge);
        }
        //加入新的边, 双端加
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        //更新存放所有边的edges成员变量
        edges.add(edge);
    }


    //删除边
    @Override
    public void removeEdge(V from, V to) {
        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null) return;
        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) return;
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            //删除存放所有边的edges成员变量中的edge
            edges.remove(edge);
        }
    }

    //添加顶点
    @Override
    public void addVertex(V v) {
        if (vertices.containsKey(v)) return;
        vertices.put(v, new Vertex<>(v));
    }

    //删除顶点
    @Override
    public void removeVertext(V v) {
        //删除顶点
        Vertex<V, E> vertex = vertices.remove(v);
        if (vertex == null) return;
        //删除边
        //1， 删除从该顶点除去的边
        //注意 不能直接在遍历的时候删除元素
        //必须只能调用iterator的remove()方法
        for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext(); ) {
            Edge<V, E> edge = iterator.next();
            edge.to.inEdges.remove(edge);
            iterator.remove();//将遍历到的元素edge从集合vertex.outEdges中删除
            edges.remove(edge);//将edge从所有边的集合edges中删除
        }
        //2， 删除进入该顶点的边
        for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext(); ) {
            Edge<V, E> edge = iterator.next();
            edge.from.outEdges.remove(edge);
            iterator.remove();//将遍历到的元素edge从集合vertex.outEdges中删除
            edges.remove(edge);//将edge从所有边的集合edges中删除
        }
    }

    @Override
    public void bfs(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        Vertex<V, E> beginVertext = vertices.get(begin);
        if (begin == null) return;
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        queue.offer(beginVertext);
        visitedVertices.add(beginVertext);
        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            if (visitor.visit(vertex.value)) return;

            for (Edge<V, E> edge : vertex.outEdges) {
                if (!visitedVertices.contains(edge.to)) {
                    queue.offer(edge.to);
                    visitedVertices.add(edge.to);
                }
            }
        }
    }

    @Override
    public void dfs(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        Vertex<V, E> beginVertext = vertices.get(begin);
        if (beginVertext == null) return;
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        Stack<Vertex<V, E>> stack = new Stack<>();
        //先访问起点
        stack.push(beginVertext);
        visitedVertices.add(beginVertext);
        if (visitor.visit(beginVertext.value)) return;

        while (!stack.isEmpty()) {
            Vertex<V, E> vertex = stack.pop();
            for (Edge<V, E> edge : vertex.outEdges) {
                if (visitedVertices.contains(edge.to)) continue;
                stack.push(edge.from);
                stack.push(edge.to);
                visitedVertices.add(edge.to);
                if (visitor.visit(edge.to.value)) return;
                break;
            }
        }
    }

    //    //广度优先遍历
//    @Override
//    public void bfs(V begin) {
//        Vertex<V,E> beginVertext=vertices.get(begin);
//        if(beginVertext==null) return;
//        Set<Vertex<V,E>> visitedVertices=new HashSet<>();
//        Queue<Vertex<V,E>> queue=new LinkedList<>();
//        queue.offer(beginVertext);
//        visitedVertices.add(beginVertext);
//        while(!queue.isEmpty()){
//            Vertex<V, E> vertex = queue.poll();
//            System.out.println(vertex.value);
//            for (Edge<V, E> edge : vertex.outEdges) {
//                if(!visitedVertices.contains(edge.to)){
//                    queue.offer(edge.to);
//                    visitedVertices.add(edge.to);
//                }
//            }
//        }
//    }
//
//    //深度优先遍历
//    //非递归版-->栈实现
//    @Override
//    public void dfs(V begin) {
//        Vertex<V,E> beginVertext=vertices.get(begin);
//        if(beginVertext==null) return;
//        Set<Vertex<V,E>> visitedVertices=new HashSet<>();
//        Stack<Vertex<V,E>> stack=new Stack<>();
//        //先访问起点
//        stack.push(beginVertext);
//        visitedVertices.add(beginVertext);
//        System.out.println(beginVertext.value);
//
//        while(!stack.isEmpty()){
//            Vertex<V, E> vertex = stack.pop();
//            for(Edge<V,E> edge:vertex.outEdges){
//                if(visitedVertices.contains(edge.to)) continue;
//                stack.push(edge.from);
//                stack.push(edge.to);
//                visitedVertices.add(edge.to);
//                System.out.println(edge.to.value);
//                break;
//            }
//        }
//    }

//    //递归实现
//    @Override
//    public void dfs(V begin){
//        Vertex<V,E> beginVertext=vertices.get(begin);
//        if(beginVertext==null) return;
//        dfs(beginVertext,new HashSet<>());
//    }
//    public void dfs(Vertex<V,E> vertex,Set<Vertex<V,E>> visitedVertices){
//        System.out.println(vertex.value);
//        visitedVertices.add(vertex);//标记已经访问过的节点
//        for (Edge<V, E> edge : vertex.outEdges) {
//            if(!visitedVertices.contains(edge.to)){//没访问过的再递归调用
//                dfs(edge.to,visitedVertices);
//            }
//        }
//    }


    @Override
    public List<V> toplogcalSort() {
        List<V> list = new ArrayList<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        //创建一个hashmap用来存放所有顶点入度的数量
        Map<Vertex<V, E>, Integer> ins = new HashMap<>();
        //初始化，将度为0的节点放入队列
        //将度不为0的节点放入哈希表中（K顶点，V入度值）
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            int in = vertex.inEdges.size();
            if (in == 0) {
                queue.offer(vertex);//入队
            } else {
                ins.put(vertex, in);//初始化表中的入度值
            }
        });
        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            //拿出队列头元素的值放入结果队列中
            list.add(vertex.value);
            //遍历outEdges
            for (Edge<V, E> edge : vertex.outEdges) {
                int toIn = ins.get(edge.to) - 1;
                if (toIn == 0) {//减完为0
                    queue.offer(edge.to);
                } else {//更新表
                    ins.put(edge.to, toIn);
                }
            }
        }
        return list;
    }

    //两种算法实现最小生成树
    @Override
    public Set<EdgeInfo<V, E>> mst() {
        //return prim();
        return kruskal();
    }

    //prim算法的最小生成树
    private Set<EdgeInfo<V, E>> prim() {
        Iterator<Vertex<V, E>> it = vertices.values().iterator();
        if (!it.hasNext()) return null;
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        Set<Vertex<V, E>> addedVertices = new HashSet<>();
        Vertex<V, E> vertex = it.next();
        //迭代出来的顶点取出最短边
        //批量建堆,传一个compartor或者 边的类实现comparable接口
        addedVertices.add(vertex);
        MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);
        //int edgeSize=vertices.size()-1;
        int verticesSize = vertices.size();
        while (!heap.isEmpty() && addedVertices.size() < verticesSize) {
            Edge<V, E> edge = heap.remove();
            if (addedVertices.contains(edge.to)) continue;
            edgeInfos.add(edge.Info());
            addedVertices.add(edge.to);
            heap.addAll(edge.to.outEdges);
        }
        return edgeInfos;
    }

    //Krusksal算法的最小生成树
    private Set<EdgeInfo<V, E>> kruskal() {
        int edgeSize = vertices.size() - 1;
        if (edgeSize == -1) return null;
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator);
        //引入并查集
        GenericUnionFind<Vertex<V, E>> uf = new GenericUnionFind<>();
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            uf.makeSet(vertex);//每个顶点单独作为一个并查集
        });
        while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
            Edge<V, E> edge = heap.remove();
            //判断是否构成环
            if (uf.isSame(edge.from, edge.to)) continue;//如果在同一个集合中说明构成环
            edgeInfos.add(edge.Info());
            //如果是选中的边， 将这两个顶点加到同一个集合中去
            uf.union(edge.from, edge.to);
        }
        return edgeInfos;
    }

//    @Override
//    public Map<V, E> shortestPath(V begin) {
//        Vertex<V, E> beginVertext = vertices.get(begin);
//        if (beginVertext == null) return null;
//        Map<V, E> selectedPaths = new HashMap<>();//被拉起来的石头
//        Map<Vertex<V, E>, E> paths = new HashMap<>();
//        //初始化paths
//        for (Edge<V, E> edge : beginVertext.outEdges) {
//            paths.put(edge.to, edge.weight);
//        }
//        //从没离开桌面的石头中获取路径最短的顶点
//        while (!paths.isEmpty()) {
//            Map.Entry<Vertex<V, E>, E> minEntry = getMinPath(paths);
//            //minEntry离开桌面，
//            Vertex<V, E> minVertex = minEntry.getKey();
//            selectedPaths.put(minVertex.value, minEntry.getValue());
//            paths.remove(minVertex);
//            //对minVertex的所有outEdges进行松弛操作
//            //松弛操作即更新从起点到edge.to的最短距离
//            for (Edge<V, E> edge : minVertex.outEdges) {
//                //排除edge.to中已经离开桌面的点
//                if(selectedPaths.containsKey(edge.to.value)) continue;
//                //以前的最短路径： beginVertex到edge.to的最短距离
//                E oldWeight = paths.get(edge.to);
//                //新的最短路径：beginVertex到edge.from的最短路径+edge.weight
//                E newWeight = weightManager.add(minEntry.getValue(), edge.weight);
//                if (oldWeight == null || weightManager.compare(newWeight, oldWeight) < 0) {//新的距离小于旧的距离
//                    paths.put(edge.to, newWeight);//更新距离
//                }
//            }
//        }
//        selectedPaths.remove(begin);
//        return selectedPaths;
//    }

    //多源最短路径算法Floyd
    @Override
    public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
        Map<V, Map<V, PathInfo<V, E>>> paths=new HashMap<>();
        //初始化， 将所有的边加进map中当作当前最小边
        for (Edge<V, E> edge : edges) {
            Map<V, PathInfo<V, E>> map = paths.get(edge.from.value);
            if(map==null){
                map=new HashMap<>();
                paths.put(edge.from.value,map);
            }
            PathInfo<V,E> pathInfo=new PathInfo<>(edge.weight);
            pathInfo.edgeInfos.add(edge.Info());
            map.put(edge.to.value,pathInfo);
        }

        //三层for循环，
        vertices.forEach((V v2,Vertex<V,E> vertex2)->{
            vertices.forEach((V v1,Vertex<V,E> vertex1)->{
                vertices.forEach((V v3,Vertex<V,E> vertex3)->{
                    if(v1.equals(v2)||v2.equals(v3)||v1.equals(v3)) return;
                    //v1->v2
                    PathInfo<V, E> path12 = getPathInfo(v1,v2,paths);
                    if(path12==null) return;
                    //v2->v3
                    PathInfo<V, E> path23 = getPathInfo(v2,v3,paths);
                    if(path23==null) return;
                    //v1->v3
                    PathInfo<V, E> path13 = getPathInfo(v1,v3,paths);
                    E newWeight= weightManager.add(path12.weight,path23.weight);
                    //1,3 之间以前有路， 并且新的路径比原来路径要长
                    if(path13!=null && weightManager.compare(newWeight,path13.weight)>=0) return;
                    //1，3 之前为空
                    if(path13==null){
                        path13=new PathInfo<V,E>();
                        paths.get(v1).put(v3,path13);
                    }else{//清除原来的edgeInfos
                        path13.edgeInfos.clear();
                    }
                    path13.weight=newWeight;
                    // 将新的路径加进去
                    path13.edgeInfos.addAll(path12.edgeInfos);
                    path13.edgeInfos.addAll(path23.edgeInfos);
                });
            });
        });
        return paths;
    }

    private PathInfo<V,E> getPathInfo(V from,V to, Map<V,Map<V,PathInfo<V,E>>> paths){
        Map<V,PathInfo<V,E>> map=paths.get(from);
        return map==null?null:map.get(to);
    }

    //带路径信息和最小路径的返回
    @Override
    public Map<V, PathInfo<V, E>> shortestPath(V begin) {
        //Dijsktra算法的最小路径
        //return dijkstra(begin);
        //Bellman-Ford算法的最小路径
        return bellmanFord(begin);
    }

    public Map<V, PathInfo<V, E>> bellmanFord(V begin) {
        Vertex<V, E> beginVertext = vertices.get(begin);
        if (beginVertext == null) return null;
        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        PathInfo<V,E> beginPath=new PathInfo<>();
        beginPath.weight=weightManager.zero();
        selectedPaths.put(begin,beginPath);
        int count=vertices.size()-1;//V-1次松弛
        for (int i = 0; i < count; i++) {
            for (Edge<V, E> edge : edges) {
                PathInfo fromPath=selectedPaths.get(edge.from.value);
                if(fromPath==null) continue;
                relaxforBellmanFord(edge,fromPath, selectedPaths);
            }
        }
        selectedPaths.remove(begin);
        return selectedPaths;
    }

    /**
     *
     * @param edge 需要松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths 存放着其他点的最短路径信息（ relaxforBellmanFord）
     */
    private void relaxforBellmanFord(Edge<V,E> edge,PathInfo<V,E> fromPath, Map<V,PathInfo<V,E>> paths){
        if(fromPath.weight==null){//起点边

        }
        //以前的最短路径： beginVertex到edge.to的最短距离
        PathInfo<V, E> oldPath = paths.get(edge.to.value);
        //新的最短路径：beginVertex到edge.from的最短路径+edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) > 0) return;
        if (oldPath == null) {//以前没有路径
            oldPath = new PathInfo<>();
            paths.put(edge.to.value, oldPath);//更新距离
        }else{
            oldPath.edgeInfos.clear();//清除之前的路径信息
        }
        //新的距离小于旧的距离
        oldPath.weight = newWeight;
        //被提起来的石头前面的最短路径
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        //松弛操作的这条边的最短路径
        oldPath.edgeInfos.add(edge.Info());
        //paths.put(edge.to, oldPath);//更新距离
    }



    public Map<V, PathInfo<V, E>> dijkstra(V begin) {
        Vertex<V, E> beginVertext = vertices.get(begin);
        if (beginVertext == null) return null;
        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();//被拉起来的石头
        Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        //初始化paths
        for (Edge<V, E> edge : beginVertext.outEdges) {
            PathInfo<V, E> path = new PathInfo<>();
            path.weight = edge.weight;
            path.edgeInfos.add(edge.Info());
            paths.put(edge.to, path);
        }
        //从没离开桌面的石头中获取路径最短的顶点
        while (!paths.isEmpty()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
            //minEntry离开桌面，
            Vertex<V, E> minVertex = minEntry.getKey();
            PathInfo<V,E> minPath=minEntry.getValue();
            selectedPaths.put(minVertex.value, minPath);
            paths.remove(minVertex);
            //对minVertex的所有outEdges进行松弛操作
            //松弛操作即更新从起点到edge.to的最短距离
            for (Edge<V, E> edge : minVertex.outEdges) {
                //排除edge.to中已经离开桌面的点
                if (selectedPaths.containsKey(edge.to.value)) continue;
                relaxForDijkstra(edge,minPath,paths);
            }
        }
        selectedPaths.remove(begin);
        return selectedPaths;
    }

    //松弛操作

    /**
     *
     * @param edge 需要松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths 存放着其他点的最短路径信息（ Dijkstra来说就是还没有离开桌面的点）
     */
    private void relaxForDijkstra(Edge<V,E> edge,PathInfo<V,E> fromPath, Map<Vertex<V,E>,PathInfo<V,E>> paths){
        //以前的最短路径： beginVertex到edge.to的最短距离
        PathInfo<V, E> oldPath = paths.get(edge.to);
        //新的最短路径：beginVertex到edge.from的最短路径+edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) > 0) return;
        if (oldPath == null) {//以前没有路径
            oldPath = new PathInfo<>();
            paths.put(edge.to, oldPath);//更新距离
        }else{
            oldPath.edgeInfos.clear();//清除之前的路径信息
        }
        //新的距离小于旧的距离
        oldPath.weight = newWeight;
        //被提起来的石头前面的最短路径
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        //松弛操作的这条边的最短路径
        oldPath.edgeInfos.add(edge.Info());
        //paths.put(edge.to, oldPath);//更新距离
    }


    //从paths的map里面挑出路径最短的顶点
    private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getMinPath(Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> it = paths.entrySet().iterator();
        Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = it.next();
        while (it.hasNext()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> entry = it.next();
            if (weightManager.compare(entry.getValue().weight, minEntry.getValue().weight) < 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }

    private static class Vertex<V, E> {
        V value;
        //进本顶点的边
        Set<Edge<V, E>> inEdges = new HashSet<>();
        //出本顶点的边
        Set<Edge<V, E>> outEdges = new HashSet<>();

        public Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            //重写equals方法
            //value值相等就认为顶点是相当的
            return Objects.equals(value, (((Vertex<V, E>) obj).value));
        }

        @Override
        public int hashCode() {
            return value == null ? 0 : value.hashCode();
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    private static class Edge<V, E> {
        Vertex<V, E> from;
        Vertex<V, E> to;
        E weight;

        public Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        EdgeInfo<V, E> Info() {
            return new EdgeInfo<>(from.value, to.value, weight);
        }

        @Override
        public boolean equals(Object obj) {
            Edge<V, E> edge = (Edge<V, E>) obj;
            //重写equals方法；
            //from 和to 一样就认为这两个边对象是一样的
            return Objects.equals(from, edge.from) &&
                    Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return from.hashCode() * 31 + to.hashCode();
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }


    public void print() {
        System.out.println("【顶点】：=========");
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            System.out.println(v);
            System.out.println("out-->");
            System.out.println(vertex.outEdges);
            System.out.println("in--<");
            System.out.println(vertex.inEdges);
        });

        System.out.println("【边】：=========");
        edges.forEach((Edge<V, E> edge) -> {
            System.out.println(edge);
        });
    }
}
